package java_thinking.unit_16.source;

import java.util.Arrays;

/**
 * @Desc:
 * @author: cww
 * @DateTime: 2019/4/24 8:53
 */

public class Exercise {

    public static void main(String[] args) {
        int[] a1 = {5,9,1,1,2,9,8,1,3,5,15,22,1,8};
        int[] a2 = {5,9,1,1,2,9,8,1,3,5,15,22,1,8};
        int[] a3 = {5,9,1,1,2,9,8,1,3,5,15,22,1,8};
        int[] a4 = {5,9,1,1,2,9,8,1,3,5,15,22,1,8};
        singleSwapSort(a1);
        System.out.println(Arrays.toString(a1));
        fillSort(a2);
        System.out.println(Arrays.toString(a2));
        forwardScanSort(a3);
        System.out.println(Arrays.toString(a3));
        div3ScanSort(a4);
        System.out.println(Arrays.toString(a4));
    }

    /**
     * 双端扫描
     * @param items
     */
    public static void singleSwapSort(int[] items) {
        singleSwapSort(items,0,items.length -1);
    }
    public static void singleSwapSort(int[] items, int start, int end) {
        if (start < end) {
            int pivot = items[start];
            int i = start + 1, j = end;
            while (i <= j) {
                //一直走到比pivot大的位置
                while (i <= j && items[i] < pivot) {
                    i++;
                }
                //一直走到比pivot小的位置
                while (i <= j && items[j] >= pivot) {
                    j--;
                }
                if (i <= j) {
                    swap(items, i, j);
                }
            }
            swap(items, start, j);
            singleSwapSort(items, start, j - 1);
            singleSwapSort(items, j+1, end);
        }
    }


    /**
     * 赋值填充
     * @param items
     */
    public static void fillSort(int[] items) {
        fillSort(items, 0, items.length - 1);
    }
    public static void fillSort(int[] items, int start, int end){
        if (start < end) {
            int pivot = items[start];
            int i = start, j = end;
            while (i < j) {
                //右边找到比pivot小的指针
                while (i < j && items[j] > pivot) {
                    j--;
                }
                //找到后与pivot互换
                items[i] = items[j];
                //从左找比pivot大的指针
                while (i < j && items[i] <= pivot) {
                    i++;
                }
                //找到后与j互换
                items[j] = items[i];
            }
            //最后把pivot放到i与j碰撞处
            items[i] = pivot;
            fillSort(items, start, i-1);
            fillSort(items, i + 1, end);
        }
    }

    public static void forwardScanSort(int[] items) {
        forwardScanSort(items, 0 ,items.length - 1);
    }

    /**
     * 单向扫描划分方式
     * j扫描时遇到小于pivot的元素，i++，并将i元素与j元素进行交换，然后扫描下一个元素
     * @param items
     * @param start
     * @param end
     */
    public static void forwardScanSort(int[] items, int start, int end) {
        if (start < end ) {
            int pivot = items[start];
            int i = start, j = start + 1;
            while (j <= end) {
                if (items[j] < pivot) {
                    i++;
                    swap(items, i , j);
                }
                j++;
            }
            //整个序列扫描完成后，将第一个元素pivot与小于pivot的元素的最后一个进行交换。
            swap(items, start, i);
            forwardScanSort(items, start, i - 1);
            forwardScanSort(items, i + 1, end);
        }
    }

    /**
     * 三分单向扫描优化
     * 优化了: 1.数组里面有些元素是一样的，单轴快排没有起到划分
     *         2.避免了普通三分单向扫描多于的替换动作
     * @param items
     */
    public static void div3ScanSort(int[] items) {
        div3ScanSort(items, 0, items.length - 1);
    }

    public static void div3ScanSort(int[] items , int start, int end) {
        if (start < end) {
            int pivot = items[start];
            int i = start, j = end, k = start + 1;
            //k<j就一直把k往右走
            OUT_LOOP : while (k <= j) {
                // < pivot的放左边，i++
                if (items[k] < pivot) {
                    swap(items, k, i);
                    i++;
                } else if (items[k] == pivot) {
                    k++;
                } else {
                    //到这个else里items[k]已经是>pivot了
                    while (items[j] > pivot) {
                        j--;
                        if (k > j) {
                            break OUT_LOOP;
                        }
                    }
                    //当items[j]比pivot小，先把比pivot大的items[k]与j替换再把items[k]放到i区域
                    if (items[j] < pivot) {
                        swap(items, k, j);
                        swap(items, i, k);
                        i++;
                    }
                    k++;
                }
            }
            div3ScanSort(items, start, i - 1);
            div3ScanSort(items, j + 1, end);
        }
    }

    public static void swap(int[] items, int i, int j) {
        int tmp = items[i];
        items[i] = items[j];
        items[j] = tmp;
    }
}
